#pragma once
#include"FileCompress.h"
#include<vector>
#include<queue>

template<class W>
struct HuffmanTreeNode
{
    HuffmanTreeNode<W>*_left;
    HuffmanTreeNode<W>*_right;
    HuffmanTreeNode<W>*_parent;
    W _weight;

    HuffmanTreeNode(const W&weight)
        :_weight(weight)
        , _left(NULL)
        , _right(NULL)
        , _parent(NULL)
    {}
};


template<class W>
class HuffmanTree
{
    typedef HuffmanTreeNode<W> HTNode;
public:
    HuffmanTree()
        :_root(NULL)
    {}

    struct NodeCompare
    {
        bool operator()(const HTNode* l, const HTNode*r)
        {
            return l->_weight > r->_weight;
        }
    };

    HuffmanTree(W*weight, size_t n, const W& flag)
    {
        //用NodeCompare比较，将元素顺序从小到大
        priority_queue<HTNode*, vector<HTNode*>, NodeCompare> maxheap;

        for (size_t i=0;i<n;++i)
        {
            if(weight[i]!=flag)
                maxheap.push(new HTNode(weight[i]));
        }

        //建堆的时候，从队列取出两个元素根据他们的count的和创建parent，然后再把parent扔回队列，继续下次
        while (maxheap.size() > 1)
        {
            HTNode*left = maxheap.top();
            maxheap.pop();
            HTNode*right = maxheap.top();
            maxheap.pop();
            HTNode*parent = new HTNode(left->_weight + right->_weight);
            parent->_left = left;
            parent->_right = right;
            left->_parent = parent;
            right->_parent = parent;
            maxheap.push(parent);
        }
        _root = maxheap.top();
    }


    HTNode* GetRoot()
    {
        return _root;
    }

    ~HuffmanTree()
    {
        //先将左右孩子delete了，再去delete根节点
        Destory(_root);
        _root = NULL;
    }

    void Destory(HTNode*root)
    {
        if (root == NULL)
        {
            return;
        }
        Destory(root->_left);
        Destory(root->_right);
        delete root;
    }

protected:
    HTNode* _root;

private:
    HuffmanTree(const HuffmanTree<W>& t);
    HuffmanTree<W>& operator=(const HuffmanTree<W>&t);
};